/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item55;

import org.junit.Assert;
import org.junit.Test;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:TreeDepth.java v1.0 2018/8/6 上午1:44 LvJing Exp $
 */
public class TreeDepth {

    /**
     * 面试题55：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
     * 思路：以根节点为起点，计算左子树深度，左子树又是一个递归，以左子树为根节点进行同样计算，右子树一样，最后比较左右子树最大的返回。
     */
    public class Solution {
        public int TreeDepth(TreeNode root) {
            if (root == null)
                return 0;

            int left = TreeDepth(root.left);
            int right = TreeDepth(root.right);
            if (left < right)
                return right + 1;
            return left + 1;
        }
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    @Test
    public void test01() {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(8, new TreeNode(6, new TreeNode(5), new TreeNode(7)),
                new TreeNode(10));

        Assert.assertEquals(3, solution.TreeDepth(root));
    }
}
